package com.mlh.backtracking;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author 缪林辉
 * @date 2024/4/3 15:03
 * @DESCRIPTION
 */
// 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
// 你可以按 任何顺序 返回答案。
public class Combine {
    //看代码随想录写出
    //回溯算法用抽象的树结构来分析就很容易想明白
    LinkedList<Integer>path=new LinkedList<>();
    List<List<Integer>> res=new ArrayList<>();
    public List<List<Integer>> method1(int n, int k) {
        recursion(1,n,k);
        return res;
    }
    public void recursion(int head,int n,int k){//head为搜索的起始位置  n为末尾位置  k是还需要选取几个数
        if(k<=0){//k=0时，表示不在需要选取数字，则将此时的集合加入到res中
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = head; i <=n-(k-1) ; i++) {
            path.add(i);//选取i
            recursion(i+1,n,k-1);//防止重复，从i+1继续递归，此时需要选取的数的数量-1
            path.removeLast();//删除i，进行下轮循环，也就是回溯
        }
    }
}
